package dp;

public class _05_63_不同路径Ⅱ {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
       	int m = obstacleGrid.length;
    	int n = obstacleGrid[0].length;
    	int dp[][] = new int[m][n];
    	// 首列元素初始化，如果遇到障碍则后面的路都不能走了
    	for(int i = 0; i < m; i++) {
    		if(obstacleGrid[i][0] == 1) {
    			break;
    		}
    		dp[i][0] = 1;
    	}
    	// 首行元素初始化，如果遇到障碍则后面的路都不能走了
    	for(int i = 0; i < n; i++) {
    		if(obstacleGrid[0][i] == 1) {
    			break;
    		}
    		dp[0][i] = 1;
    	}
    	
    	// 障碍在dp数组的值默认是1，遇到障碍则不计算路径
    	for(int i = 1; i < m; i++) {
    		for(int j = 1; j < n; j++) {
    			if(obstacleGrid[i][j] != 1) {
    				dp[i][j] = dp[i-1][j] + dp[i][j-1];
    			}
    		}
    	}

    	return dp[m-1][n-1];
    }
    public static void main(String[] args) {
    	int[][] obstacleGrid =  {
    			{0,1},
    			{0,0}};
		System.out.println(uniquePathsWithObstacles(obstacleGrid));
	}
}
